package Solution.problem070;

/**
 * @program Leetcode
 * @description: 题意：爬台阶问题。每次能爬一个或两个台阶，问一个有n个台阶的话，一共有几种方法爬到顶端。

 *
 * 思路：
 *
 * 　　n<=1，此时只有一种。
 *
 * 　　n>1时，对于每一个台阶i，要到达台阶，最后一步都有两种方法，从i-1迈一步，或从i-2迈两步。
 *
 * 　　也就是说到达台阶i的方法数=达台阶i-1的方法数+达台阶i-2的方法数。所以该问题是个DP问题。
 *
 *  递归容易超时，这应该是这道题的坑吧，还是循环遍历算一下吧
 * @author: lishangsheng
 * @create: 2019/06/09 22:14
 */
public class Solution {
    /**
     * 速度挺快，但是内存空间用的多
     * @param n
     * @return
     */
    public static int climbStairs(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0 || n == 1) {
            return 1;
        }
        /*   return climbStairs(n-1)+climbStairs(n-2);*/

        int[] result = new int[n];
        result[0] = 1;
        result[1] = 2;
        for(int i=2;i<n;i++){
            result[i]= result[i-1]+ result[i-2];
        }
        return result[n-1];
    }

    /**
     * 减少一下内存空间
     * @param n
     * @return
     */
    public static int climbStairs2(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0 || n == 1) {
            return 1;
        }
        /*   return climbStairs(n-1)+climbStairs(n-2);*/

        int n1 = 1;
        int n2 = 2;
        while (n > 2) {
            int sum = n1 + n2;
            n1 = n2;
            n2 = sum;
            n--;
        }
        return n2;
    }

    public static void main(String[] args){
       System.out.println( climbStairs2(44)==1134903170);
       System.out.println( climbStairs2(2));
    }
}
